In a typical memory device, data is stored at each address. The address is specified to read data stored in the specified address. In an associative memory device, data similar to input data is searched and read.
A typical associative memory is a content addressable memory (CAM) configured to search a reference data base for data completely matching with search data (refer to Patent Literatures 1 to 3 and Non Patent Literatures 1 to 3, for example). The CAM, which operates completely in parallel, includes a memory cell and a comparison circuit at each memory cell. The comparison circuit compares input data with reference data in the memory cell. The CAM searches fast for reference data matching with a specified destination IP address or MAC address. However, the CAM is useful for searching for an IP address at a network router, but is not suitable for searching for similar data.
One of technologies of searching for similar data is an associative memory having a nearest neighbor search (NNS) function. The associative memory is achieved in a digital approach (refer to Patent Literatures 4 and 5 and Non Patent Literatures 4 to 7, for example) or an analog approach (refer to Non Patent Literature 8, for example).
In general, the NNS associative memory determines whether multidimensional reference data is similar to search data. One-word reference data has N-dimensional data. One-dimensional data has M bits.
The NNS associative memory in a digital approach includes a storage circuit configured to store reference data of each dimension, a distance calculation circuit configured to calculate, as a distance, how similar reference data of each dimension is to search data, and a distance/clock number conversion circuit configured to start operation of clock signal counting in response to inputting of a trigger signal and configured to output a match signal indicating the timing of counting a clock number corresponding to a distance calculated by the distance calculation circuit. Distance/clock number conversion circuits are connected to each other in series and a match signal output from the distance/clock number conversion circuit in the front stage is turned into a trigger signal for the distance/clock number conversion circuit in the rear stage. In the NNS associative memory, a winner detection circuit determines a match signal of the earliest timing from among match signals input from a plurality of distance/clock number conversion circuits, and outputs the associative result. To control whether an output from the distance/clock number conversion circuit is sent to the next distance/clock number conversion circuit or to the winner detection circuit, a reconfigurable programmable switch circuit is provided for each of the distance/clock number conversion circuits.
The NNS associative memory in an analog approach includes volatile data storage circuits of R rows and N columns configured to store reference data of R words, N pieces of D/A conversion circuits provided only for one row and configured to convert digital data into analog data, matching cells of R rows and N columns provided for each dimension and each configured to evaluate the similarity between reference data and search data by a voltage difference therebetween and output the evaluation as a current, a current-to-delay-time converter circuit configured to convert an output currents of the matching cells of each row, which is obtained by integrating currents of N pieces of matching cells, into R pieces of voltage delay signals, and a time-domain winner-take-all circuit configured to search for the earliest rising signal from among the R pieces of voltage delay signals.
The group of the inventors have developed the technology of a spin transfer torque-magnetoresistance random access memory (STT-MRAM) as a nonvolatile memory (refer to Non Patent Literatures 9 and 10, for example).